package 用最少数量的箭引爆气球;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: AirMan
 * @date: 2025/4/25 16:56
 * @description:
 */
public class Solution {
    /**
     * 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度
     * 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间
     */
    public int findMinArrowShots(int[][] points) {
        // greedy
        // 对气球按照起始位置进行排序，这样我们不需要对poins进行remove操作，只需要在合适的位置射弓之后跳过即可
        // 关键在于合适是射弓的最佳时机：记录当前交集的右边界，只要下一个气球的起始位置 大于 交集的右边界那么就需要一个弓立刻射出
        // 如果 等于 其实也可以重新更新交集的右边界（其实更新之后边界没变，但是可以跳过该轮循环，下次循环的时候进行射箭处理）
        // 局部最优：当气球出现重叠，一起射，所用弓箭最少。
        // 全局最优：把所有气球射爆所用弓箭最少。

        Arrays.sort(points, (o1, o2) -> Long.compare(o1[0], o2[0])); // 使用Long.compare防止long的整型溢出
        int result = 1; // points不为空，至少会射出一枝箭（保证最后的箭能射出去！）
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > points[i - 1][1]) {
                // 气球的起始位置 大于 交集的右边界那么就需要一个弓立刻射出
                result++;
            } else {
                // 利用 points[i][1] 记录当前交集的右边界(也可以新建一个数组进行记录，只不过会增加空间复杂度)
                points[i][1] = Math.min(points[i - 1][1], points[i][1]);
            }
        }
        return result;
    }
}